LeetCode-16-3Sum Closest

LeetCode-16-3Sum Closest

题目描述：

链接：https://leetcode-cn.com/problems/3sum-closest/

思路分析：

同样是双指针的变形，照样可以采用15题的思路，通过遍历，将一个值固定，去找l和r，使得nums[r]+nums[l] + 固定的数的和与target的差的绝对值最小。需要注意的是，本题的初始化ans = num[0]+nums[1]+nums[2]。

代码：

class Solution {
    int ans;
    public int threeSumClosest(int[] nums, int target) {
        if(nums.length < 3) return 0;
        Arrays.sort(nums);
        ans = nums[0] + nums[1] + nums[2];
        for(int i = 0; i < nums.length; i++) {
            helper(nums,i+1,nums.length-1,nums[i],target);
            if(ans == target)   return ans;
        }
        return ans;
    }
    private void helper(int[] nums, int l, int r, int num,int target) {
        if(l > r) return;
        while(l < r && r < nums.length) {
            int sum = num + nums[l] + nums[r];
            if(Math.abs(target - sum) <= Math.abs(target - ans)) {
                ans = sum;
            }
            if(sum == target) {
                return;
            }
            else if(sum > target) {
                r--;
            }
            else{
                l++;
            }
        }
    }
}

简化代码：

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        if(nums.length < 3)     return 0;
        int ans = nums[0] + nums[1] + nums[2];
        for(int i = 0; i < nums.length; i++) {
            int l = i + 1;
            int r = nums.length - 1;
            while(l < r && r < nums.length) {
                int sum = nums[i] + nums[r] + nums[l];
                if(Math.abs(target - ans) >= Math.abs(target - sum)) {
                    ans = sum;
                }
                if(sum == target) {
                    return sum;
                }
                else if(sum > target) {
                    r--;
                }
                else {
                    l++;
                }
            }
        }
        return ans;
    }
}

AC记录：

赏

谢谢你请我吃糖果